import javax.swing.*;
import java.util.*;

public class TreeNode {
       public int val;
       public TreeNode left;
       public TreeNode right;
       TreeNode() {}
       TreeNode(int val) { this.val = val; }
       TreeNode(int val, TreeNode left, TreeNode right) {
           this.val = val;
           this.left = left;
           this.right = right;
       }
 }

class Solution {
    /**
     * 给你二叉树的根节点 root,返回它节点值的前序遍历
     * 解法 1:递归解法
     * @param root 根节点
     * @return 返回前序遍历序列
     */
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        //树为空,返回空列表
        if (root == null) return list;
        //根
        list.add(root.val);
        //左
        list.addAll(preorderTraversal(root.left));
        //右
        list.addAll(preorderTraversal(root.right));
        return list;
    }
    /**
     * 给你二叉树的根节点 root,返回它节点值的前序遍历
     * 解法 2:迭代解法
     * @param root 根节点
     * @return 返回前序遍历序列
     */
    public List<Integer> preorderTraversal2(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        //树为空则返回空表
        if (root == null) return list;
        Stack<TreeNode> stack = new Stack<>();
        //node标记当前节点
        TreeNode node = root;
        //当前节点非空或栈非空,遍历树
        while (!stack.isEmpty() || node != null) {
            //依次将左侧节点压栈
            while (node != null) {
                list.add(node.val);
                stack.push(node);
                node = node.left;
            }
            //左侧节点遍历结束,node重新指向左侧最后一个节点
            node = stack.pop();
            //node向右侧移动
            node = node.right;
        }
        return list;
    }
}